#include<stdio.h>

/*
 * 本程序是堆排序的示例
 *
 * 作者：Tmacy
 * 时间：2013-11-26
 *
 */


int heap_size ;

void max_heapify(int *a,int i);
void build_max_heap(int *a,int size_a);
void heap_sort(int *a,int size_a);

int main(int argc, const char *argv[])
{

    int a[10]  = {4,3,4,10,31,193,89,0,1,1};
    int size_a = sizeof(a) / sizeof(int) ;


    heap_sort(a,size_a);

    for(int i = 0;i < size_a;i++){
        printf("%d ",a[i]);
    }
    putchar(10);


    return 0;
}

//构建一个最大堆
void build_max_heap(int *a,int size_a){
    int i;
    heap_size = size_a;
    
    for(i = size_a / 2 ;i >= 0;i--){
        max_heapify(a,i);
    }

}
//从下标i开始，保证a[i]之后的所有元素符合最大堆的规则
void max_heapify(int *a,int i){
    int left    = 2 * i;            //完全二叉树标号为i的左孩子标号为2×i
    int right   = 2 * i + 1;        //完全二叉树标号为i的右孩子标号为2×i + 1

    int largest = 0;

    if( left < heap_size && a[left] > a[i]){
        largest = left;
    }else{
        largest = i;
    }

    if( right < heap_size && a[right] > a[largest]){
        largest = right;
    }

    if( largest != i ){
       a[largest] ^= a[i];
       a[i] ^= a[largest];
       a[largest] ^= a[i];

       max_heapify(a,largest);
    }
}
/*
 *   堆排序:构建最大堆，此时，树根所在位置就是这个堆中最大值，
 *   将其和最后位置交换,并将其从堆中
 *   移除。依次迭代，得到从小到大的排序
 */
void heap_sort(int *a,int size_a){

    build_max_heap(a,size_a);

    int i;
    for(i = size_a - 1;i >= 1;i--){

        a[0] ^= a[i];
        a[i] ^= a[0];
        a[0] ^= a[i];
        heap_size--;

        max_heapify(a,0);
    }
}
